# 时间O(n^2)
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        max_val = 0
        for i in range(1,len(nums)+1):
            max_val = max(i, max_val)
            if i not in nums:
                return i 
        return max_val + 1

# O（n） O(n)
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = Counter()
        for x in nums:
            cnt[x] += 1
        print(cnt)
        max_val = 0
        for i in range(1,1 + n):
            max_val = max(i, max_val)
            if i not in cnt:
                return i 
        return max_val + 1
#O(n) 1
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            # 如果当前学生的学号在 [1,n] 中，但（真身）没有坐在正确的座位上
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                # 那么就交换 nums[i] 和 nums[j]，其中 j 是 i 的学号
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
        
        # 找第一个学号与座位编号不匹配的学生
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        
        # 所有学生都坐在正确的座位上
        return n + 1